
#include "BinaryTree.h"

using namespace std;



void TreeDiffValue(BinaryTreeNode* pRoot, int &max, int &min)
{
	if(pRoot==NULL)
		return;
	int v = pRoot->m_nValue;
	if(v>max)
		max = v;
	else if(v<min)
		min = v;
	
	TreeDiffValue(pRoot->m_pLeft, max, min);
	TreeDiffValue(pRoot->m_pRight, max, min);
}
//求二叉树两个节点间最大的差的绝对值
int TreeDiffValue(BinaryTreeNode* pRoot)
{
	if(pRoot==NULL)
		return 0;
	int max = pRoot->m_nValue;
	int min = pRoot->m_nValue;
	TreeDiffValue(pRoot->m_pLeft, max, min);
	TreeDiffValue(pRoot->m_pRight, max, min);
	return max-min;
	
}

// ====================测试代码====================
void Test(BinaryTreeNode* pRoot, int expected)
{
    int result = TreeDiffValue(pRoot);
    if(expected == result)
        printf("Test passed.\n");
    else
        printf("Test failed.\n");
}

//            1
//         /      \
//        2        3
//       /\         \
//      4  5         6
//        /
//       7
void Test1()
{
    printf("Test1 begins.\n");

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);

    ConnectTreeNodes(pNode1, pNode2, pNode3);
    ConnectTreeNodes(pNode2, pNode4, pNode5);
    ConnectTreeNodes(pNode3, NULL, pNode6);
    ConnectTreeNodes(pNode5, pNode7, NULL);

    Test(pNode1, 6);

    DestroyTree(pNode1);
}

//               1
//              /
//             2
//            /
//           3
//          /
//         4
//        /
//       5
void Test2()
{
    printf("Test2 begins.\n");

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);

    ConnectTreeNodes(pNode1, pNode2, NULL);
    ConnectTreeNodes(pNode2, pNode3, NULL);
    ConnectTreeNodes(pNode3, pNode4, NULL);
    ConnectTreeNodes(pNode4, pNode5, NULL);

    Test(pNode1, 4);

    DestroyTree(pNode1);
}

// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
void Test3()
{
    printf("Test3 begins.\n");

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);

    ConnectTreeNodes(pNode1, NULL, pNode2);
    ConnectTreeNodes(pNode2, NULL, pNode3);
    ConnectTreeNodes(pNode3, NULL, pNode4);
    ConnectTreeNodes(pNode4, NULL, pNode5);

    Test(pNode1, 4);

    DestroyTree(pNode1);
}

// 树中只有1个结点
void Test4()
{
    printf("Test4 begins.\n");

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    Test(pNode1, 0);

    DestroyTree(pNode1);
}

// 树中没有结点
void Test5()
{
    printf("Test5 begins.\n");

    Test(NULL, 0);
}


int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();


    return 0;
}


